package MonotonicStack;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * @author Lzm
 * @version 1.0
 */
public class nextGreaterElements_ {

  @Test
  public void nextGreaterElementTest(){
    int[] nums = new int[]{1,2,3,4,3};

    int[] ints = nextGreaterElements2(nums);
    for (int anInt : ints) {
      System.out.println(anInt);
    }
  }

  // 环形数组
  // 方法1: 数组扩容 如 [1,2,3] -> [1,2,3,1,2,3]
  // 方法2: 取模

  //方法1
  public int[] nextGreaterElements(int[] nums) {
    Stack<Integer> stack = new Stack<>();

    int[] result = new int[nums.length];
    int[] Result = new int[nums.length * 2];

    Arrays.fill(result,-1);
    Arrays.fill(Result,-1);

    int[] newNums = new int[nums.length * 2];
    List<Integer> list = new ArrayList<>();

    for (int i = 0 ; i < nums.length ; i++){
      newNums[i % newNums.length + nums.length] = nums[i];
      newNums[i] = nums[i];
    }

    stack.push(0);
    for (int i = 0 ;i < newNums.length ; i++){
      while (!stack.isEmpty() && newNums[i] > newNums[stack.peek()]){
        Result[stack.pop()] = newNums[i];
      }
      stack.push(i);
    }
    for (int i = 0 ; i < nums.length; i++){
      result[i] = Result[i];
    }
    return result;
  }

  //方法2
  public int[] nextGreaterElements2(int[] nums) {
    Stack<Integer> stack = new Stack<>();
    int[] result = new int[nums.length];

    Arrays.fill(result, -1);
    stack.push(0);
    for (int i = 1 ; i < nums.length * 2 ; i++){
      // 注意这里是while
      while (!stack.isEmpty() && nums[i % nums.length] > nums[stack.peek()]){
        result[stack.pop()] = nums[i % nums.length];
      }
      stack.push(i % nums.length);
    }
      return  result;
  }
}
